Dense coding scheme using superpositions of Bell-states and its NMR implementation

Dense coding using superpositions of Bell-states is proposed. The generalized Grover's algorithm is used to prepare the initial entangled states, and the reverse process of the quantum algorithm is used to determine the entangled state in the decoding measurement. Compared with the previous schemes, the superpositions of two Bell-states are exploited. Our scheme is demonstrated using a nuclear magnetic resonance (NMR) quantum computer. The corresponding manipulations are obtained. Experimental results show a good agreement between theory and experiment. We also generalize the scheme to transmit eight messages by introducing an additional two-state system.     

Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences

In the paper a single machine time-dependent scheduling problem is considered. The processing time p_j of each job is described by a function of the starting time t of the job, p_j=1+α_jt, where the job deterioration rate α_j?0 for j=0,1,…,n and t?0. Jobs are nonpreemptable and independent, there are no ready times and no deadlines. The criterion of optimality of a schedule is the total completion time.First, the notion of a signature for a given sequence of job deterioration rates is introduced, two types of the signature are defined and their properties are shown. Next, on the basis of these properties a greedy polynomial-time approximation algorithm for the problem is formulated. This algorithm, starting from an initial sequence, iteratively constructs a new sequence concatenating the previous sequence with new elements, according to the sign of one of the signatures of this sequence.Finally, these results are applied to the problem with job deterioration rates which are consecutive natural numbers, α_j=j for j=0,1,…,n. Arguments supporting the conjecture that in this case the greedy algorithm is optimal are presented.     

Stationary Analysis of a Fluid Queue Driven by Some Countable State Space Markov Chain

Motivated by queueing systems playing a key role in the performance evaluation of telecommunication networks, we analyze in this paper the stationary behavior of a fluid queue, when the instantaneous input rate is driven by a continuous-time Markov chain with finite or infinite state space. In the case of an infinite state space and for particular classes of Markov chains with a countable state space, such as quasi birth and death processes or Markov chains of the G/M/1 type, we develop an algorithm to compute the stationary probability distribution function of the buffer level in the fluid queue. This algorithm relies on simple recurrence relations satisfied by key characteristics of an auxiliary queueing system with normalized input rates.      

半定规划问题的一种新的预测-校正算法

本文首先将半定规划转化为一个变分不等式问题,在满足单调性和Lipschitz连续的条件下,提出了一种基于Korpelevich-Khobotv算法的新的预测-校正算法,并给出算法的收敛性分析.     

A CLASS OF RANDOM NUMBER GENERATORS BASED ON WEYL SEQUENCE

The generation of good pseudo-random numbers is the base of many important fields in scientific computing, such as randomized algorithms and numerical solution of stochastic differential equations. In this paper, a class of random number generators （RNGs） based on Weyl sequence is proposed. The uniformity of those RNGs is proved theoretically. Statistical and numerical computations show the efficiency of the methods.     

Computational modeling of elastic and plastic multiple cracks by the fundamental solutions

The fundamental solutions of elasticity are used to establish a numerical method for elastic and plastic multiple crack problems in two dimensions. The continuous distributions of the point forces, dislocations, and the plastic sources are used systematically to model the crack, non-crack boundary, and the plastic deformation. Use of these singularities are guided strictly by the physical interpretation of the problem. We adopt Muskhelishvili's complex variable formalism that facilitate the analytical evaluation of the integrals representing the continuous distributions of the singularities. The resulting numerical method is concise and accurate enough to be used for elastic and plastic multiple crack problems.     

连续时间遗传算法模型及其强收敛性分析

本文在隐马尔可夫链的框架下利用隐马尔可夫链{Xt:t∈[0,∞)}的观测链的概率分布提出一个连续化遗传算法模型，并给出其一个强收敛结果，讨论了其离散骨架的性质。     

Cluster algorithms for anisotropic quantum spin models

We present cluster Monte Carlo algorithms for theXYZ quantum spin models. In the special case ofS=1/2, the new algorithm can be viewed as a cluster algorithm for the 8-vertex model. As an example, we study theS=1/2XY model in two dimensions with a representation in which the quantization axis lies in the easy plane. We find that the numerical autocorrelation time for the cluster algorithm remains of the order of unity and does not show any significant dependence on the temperature, the system size, or the Trotter number. On the other hand, the autocorrelation time for the conventional algorithm strongly depends on these parameters and can be very large. The use of improved estimators for thermodynamic averages further enhances the efficiency of the new algorithms.     

Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function

The paper present a linear-time algorithm for solving the two machine open shop scheduling problem to minimize an arbitrary regular penalty function depending on the lengths of periods during which the machines are used. Both the preemptive and the nonpreemptive cases of the problem are considered.     

Open shop problems with unit time operations

We show that them-machine open shop problem in which all operations have unit processing times can be polynomially transformed to a special preemptive scheduling problem onm identical parallel machines. Many results published recently as well as some new results are derived by using this transformation. The new results include solutions of open problems mentioned in a recent paper by Kubiak et al. p]A similar relationship is derived between no-wait open shop problems with unit time operations andm-machine problems with jobs having unit processing times.This work was supported by Deutsche Forschungsgemeinschaft (Project JoPTAG).